/**
 * 
 * 寻找第K大
 * 
 * 描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 
O
(
n
l
o
g
n
)
O(nlogn)，空间复杂度 
O
(
1
)
O(1)
数据范围：
0
≤
n
≤
1000
0≤n≤1000， 
1
≤
K
≤
n
1≤K≤n，数组中每个元素满足 
0
≤
v
a
l
≤
10000000
0≤val≤10000000
 */
public class 寻找第K大 {
    
    public static void main(String[] args) {
        
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    public static int findKth (int[] a, int n, int K) {
        // write code here

        //快拍 可以使用 Arrays.stored

        return findK(a, 0, n-1, K);
    }

    private static int findK(int[] a, int left, int right, int K){

        if (left <= right) {
            int pivot = partition(a, left, right);
 
            if (pivot == K - 1) {
                return a[pivot];
            } else if (pivot < K - 1) {
                return findK(a, pivot + 1, right, K);
            } else {
                return findK(a, left, pivot - 1, K);
            }
        }
        return -1;

    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
 
        while (left < right) {
            while (left < right && arr[right] <= pivot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] >= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

}
